function diff(oldTree, newTree) {
  let patches = {};
  let index = 0;
  // 递归树，比较后的结果放到补丁包中
  walk(oldTree, newTree, index, patches);
  return patches;
}

function diffChildren(oldChildren = [], newChildren, index, patches) {
  oldChildren.forEach((child, idx) => {
    walk(child, newChildren[idx], ++Index, patches);
  });
}

function isString(node) {
  return Object.prototype.toString.call(node) === '[object String]';
}

const ATTRS = 'ATTRS';
const TEXT = 'TEXT';
const REMOVE = 'REMOVE';
const REPLACE = 'REPLACE';

let index = 0;
function walk(oldNode, newNode, index, patches) {
  // 每一个元素都有一个补丁对象
  let currentPatch = [];

  if (!newNode) {
    currentPatch.push({
      type: REMOVE,
      index: index,
    });
  } else if (isString(oldNode) && isString(newNode)) {
    // 文本节点单独判断
    if (oldNode !== newNode) {
      currentPatch.push({
        type: TEXT,
        text: newNode,
      });
    }
  } else if (oldNode.type === newNode.type) {
    // 比较属性是否有差异
    let attrs = diffAttr(oldNode.props, newNode.props);

    if (Object.keys(attrs).length > 0) {
      // 如果属性有差异，将属性差异保存到补丁包
      currentPatch.push({
        type: ATTRS,
        attrs,
      });
    }

    // 如果有子节点，遍历子节点
    diffChildren(oldNode.children, newNode.children, index, patches);
  } else {
    // 节点被替换了
    currentPatch.push({
      type: REPLACE,
      newNode,
    });
  }

  if (currentPatch.length > 0) {
    // 当前元素确实有补丁
    // 将元素和补丁对应起来
    patches[index] = currentPatch;
  }
}

function diffAttr(oldAttrs, newAttrs) {
  let patch = {};
  for (let key in oldAttrs) {
    if (oldAttrs[key] !== newAttrs[key]) {
      patch[key] = newAttrs[key];
    }
  }
  for (let key in newAttrs) {
    if (!oldAttrs.hasOwnProperty(key)) {
      patch[key] = newAttrs[key];
    }
  }

  return patch;
}
